#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# ======================================================
# @File:      : test76
# @Author     : forward_huan
# @Date       : 2024/11/17 17:31
# @Desc       :
# ======================================================
import re


class Solution:

    @staticmethod
    def cal_count(t):
        ret = {}
        for ch in t:
            if ch not in ret:
                ret[ch] = 1
            else:
                ret[ch] += 1
        return ret

    @staticmethod
    def add_data(data: dict, ch):
        if ch in data:
            data[ch] += 1
        else:
            data[ch] = 1

    @staticmethod
    def pop_data(data: dict, ch):
        data[ch] -= 1
        if data[ch] == 0:
            data.pop(ch)

    @staticmethod
    def is_match(win_dict: dict, match_dict: dict):
        for ch, cnt in match_dict.items():
            if ch not in win_dict or win_dict[ch] < cnt:
                return False
        return True

    def minWindow(self, s: str, t: str) -> str:
        if len(t) > len(s):
            return ""
        left, right, result = 0, 0, []
        win_dict, match_dict = {}, self.cal_count(t)
        while right < len(s):
            while not self.is_match(win_dict, match_dict) and right < len(s):
                self.add_data(win_dict, s[right])
                right += 1
            if not self.is_match(win_dict, match_dict):
                break
            while left < right and self.is_match(win_dict, match_dict):
                self.pop_data(win_dict, s[left])
                left += 1
            result.append(s[left - 1:right])
        if not result:
            return ""
        return sorted(result, key=lambda x: len(x))[0]


print(Solution().minWindow(s="ADOBECODEBANC", t="ABC"))
print(Solution().minWindow(s="a", t="b"))
